package com.javatest;

import java.util.*;

/**
 * @author LL
 * 打印出杨辉三角形（要求打印出10行）
 *杨辉三角最大的特性就是每个数字都是该数字肩上的两个数字之和
 * @create 2020-12-22 17:17
 */
public class Subject22 {

    public static void yangHuiTriangle() {
//        int arr[][] = new int[10][10];
//        for (int i = 0;i < arr.length; i++) {
//            for (int j=0;j<=i;j++){
//                if (j==0|| j==i) {
//                    arr[i][j]=i;
//                }else{
//                    arr[i][j] = arr[i - 1][j - 1] + arr[i-1][j];
//                }
//                System.out.print(arr[i][j]+"\t");
//            }
//            System.out.println();
//        }
        int[][] ints = new int[10][10];
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j <= i; j++) {
                if (i - 1 < 0 || j - 1 < 0) {
                    ints[i][j] = 1;
                } else {
                    ints[i][j] = ints[i - 1][j - 1] + ints[i - 1][j];
                }
                System.out.print(ints[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void yanHih() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            a[i][i] = 1;
            a[i][0] = 1;
        }
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) {
                a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

    //迭代方法
    public static List<List<Integer>> generateTrangle(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> subList = new ArrayList<>();
            list.add(subList);
            for (int j = 0; j < i + 1; j++) {
                if (j == i || j == 0) {//每行的最左边和最右边的数字都是1
                    subList.add(1);
                } else {
                    //递推关系
                    subList.add((list.get(i - 1).get(j - 1) + list.get(i - 1).get(j)));
                }
            }
        }
        return list;
    }

    //递归
    public static List<List<Integer>> generateTriangleByRecursive(int numRow) {
        List<List<Integer>> list = new ArrayList<>();
        Map<Integer, Map<Integer, Integer>> cacheMap = new HashMap<>();
        for (int i = 0; i < numRow; i++) {
            List<Integer> subList = new ArrayList<>();
            for (int j = 0; j < i + 1; j++) {
                subList.add(generate_Triangle_by_recursive(i, j, cacheMap));
            }
            list.add(subList);
        }
        return list;
    }

    private static int generate_Triangle_by_recursive(int i, int j,Map<Integer, Map<Integer, Integer>> cacheMap) {
        if (cacheMap.containsKey(i) && cacheMap.get(i).containsKey(j)) {
            return cacheMap.get(i).get(j);
        }
        int result;
        if (j == 0 || j == i) {
            result = 1;
        } else {
            result = (generate_Triangle_by_recursive(i - 1, j - 1, cacheMap) + generate_Triangle_by_recursive( i - 1, j, cacheMap));
        }
        if (!cacheMap.containsKey(i)) {
            Map<Integer, Integer> map = new HashMap<>();
            cacheMap.put(i, map);
        }
        cacheMap.get(i).put(j, result);
        return result;
    }

    //得到第index行杨辉三角
    public static List<Integer> getRow(int rowIndex) {
        List<List<Integer>> list = new ArrayList<>();
        for(int i=0;i<rowIndex+1;i++){
            List<Integer> subList = new ArrayList<>();
            list.add(subList);
            for(int j=0;j<i+1;j++){
                if(j==i||j==0){//first and end
                    subList.add(1);
                }else{
                    subList.add((list.get(i-1).get(j-1)+list.get(i-1).get(j)));
                }
            }
        }
        return list.get(rowIndex);
    }

    public static void yangHui(){
        int[][] yangHui = new int[10][];
        for (int i = 0; i < yangHui.length; i++) {
            yangHui[i] = new int[i+1];
            yangHui[i][0] = yangHui[i][i] = 1;
            for (int j = 1; j < yangHui[i].length-1; j++) {
                yangHui[i][j] = yangHui[i-1][j-1] + yangHui[i-1][j];
            }
        }
        for (int i = 0; i < yangHui.length; i++) {
            for (int j = 0; j < yangHui[i].length; j++) {
                System.out.print(yangHui[i][j]+"    ");
            }
            System.out.println();
        }
    }

    //递归求和
    public static int sum(int num){
        if(1 == num){
            return 1;
        } else {
            int i = num + sum(num - 1);
            return i;
        }
    }

    public static int sum1(int num){
        if (1 == num) {
            return 1;
        }else {
            int i = num + sum(num - 1);
            return i;
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = generateTriangleByRecursive(7);
        for (List<Integer> list : lists) {
           // System.out.println(list.toString());
        }
        //System.out.println(getRow(10));
        yangHui();
    }


}
